Detecting a variety of anomalies caused by attacks or accidents in computer networks has been one of the real challenges for both researchers and network operators. An effective technique that could quickly and accurately detect a wide range of anomalies would be able to prevent serious consequences for system security or reliability. In this article, we characterize detection techniques on the basis of learning models and propose an unsupervised learning model for real-time anomaly detection in computer networks. We also conducted a series of experiments to examine capabilities of the proposed model by employing three well-known machine learning algorithms, namely multivariate normal distribution, k-nearest neighbor, and one-class support vector machine. The results of these experiments on real network traffic suggest that the proposed model is a promising solution and has a number of flexible capabilities to detect several types of anomalies in real time.

In this paper, we propose a new matting algorithm using local and nonlocal neighbors. We assume that K nearest neighbors satisfy the color line model that RGB distribution of the neighbors is roughly linear and combine this assumption with the local color line model that RGB distribution of local neighbors is roughly linear. Our assumptions are appropriate for various regions such as those that are smooth, contain holes or have complex color. Experimental results show that the proposed method outperforms previous propagation-based matting methods. Further, it is competitive with sampling-based matting methods that require complex sampling or learning methods.

Recently, Yuan et al. (IEEE Infocom'13, pp.2652-2660) proposed an efficient secure nearest neighbor (SNN) search scheme on encrypted cloud database. Their scheme is claimed to be secure against the collusion attack of query clients and cloud server, because the colluding attackers cannot infer the encryption/decryption key. In this letter, we observe that the encrypted dataset in Yuan's scheme can be broken by the collusion attack without deducing the key, and present a simple but powerful attack to their scheme. Experiment results validate the high efficiency of our attacking approach. Additionally, we also indicate an upper bound of collusion-resistant ability of any accurate SNN query scheme.

The classification of human motion is an important aspect of monitoring pedestrian traffic. This requires the development of advanced surveillance and monitoring systems. Methods to achieve this have been proposed using micro-Doppler radars. However, reliable long-term data and/or complicated procedures are needed to classify motion accurately with these conventional methods because their accuracy and real-time capabilities are invariably inadequate. This paper proposes an accurate and real-time method for classifying the movements of pedestrians using ultra wide-band (UWB) Doppler radar to overcome these problems. The classification of various movements is achieved by extracting feature parameters based on UWB Doppler radar images and their radial velocity distributions. Experiments were carried out assuming six types of pedestrian movements (pedestrians swinging both arms, swinging only one arm, swinging no arms, on crutches, pushing wheelchairs, and seated in wheelchairs). We found they could be classified using the proposed feature parameters and a k-nearest neighbor algorithm. A classification accuracy of 96% was achieved with a mean calculation time of 0.55s. Moreover, the classification accuracy was 99% using our proposed method for classifying three groups of pedestrian movements (normal walkers, those on crutches, and those in wheelchairs).

In this letter, the problem of feature quantization in robust hashing is studied from the perspective of approximate nearest neighbor (ANN). We model the features of perceptually identical media as ANNs in the feature set and show that ANN indexing can well meet the robustness and discrimination requirements of feature quantization. A feature quantization algorithm is then developed by exploiting the random-projection based ANN indexing. For performance study, the distortion tolerance and randomness of the quantizer are analytically derived. Experimental results demonstrate that the proposed work is superior to state-of-the-art quantizers, and its random nature can provide robust hashing with security against hash forgery.

In this paper, we propose a hardware solution for overcoming the problem of high computational demands in a nearest neighbor (NN) based multi-prototype learning system. The multiple prototypes are obtained by a high-speed K-means clustering algorithm utilizing a concept of software-hardware cooperation that takes advantage of the flexibility of the software and the efficiency of the hardware. The one nearest neighbor (1-NN) classifier is used to recognize an object by searching for the nearest Euclidean distance among the prototypes. The major deficiency in conventional implementations for both K-means and 1-NN is the high computational demand of the nearest neighbor searching. This deficiency is resolved by an FPGA-implemented coprocessor that is a VLSI circuit for searching the nearest Euclidean distance. The coprocessor requires 12.9% logic elements and 58% block memory bits of an Altera Stratix III E110 FPGA device. The hardware communicates with the software by a PCI Express (4) local-bus-compatible interface. We benchmark our learning system against the popular case of handwritten digit recognition in which abundant previous works for comparison are available. In the case of the MNIST database, we could attain the most efficient accuracy rate of 97.91% with 930 prototypes, the learning speed of 1.310-4 s/sample and the classification speed of 3.9410-8 s/character.

In the task of face recognition, a challenging issue is the one sample problem, namely, there is only one training sample per person. Principal component analysis (PCA) seeks a low-dimensional representation that maximizes the global scatter of the training samples, and thus is suitable for one sample problem. However, standard PCA is sensitive to the outliers and emphasizes more on the relatively distant sample pairs, which implies that the close samples belonging to different classes tend to be merged together. In this paper, we propose two-stage block-based whitened PCA (TS-BWPCA) to address this problem. For a specific probe image, in the first stage, we seek the K-Nearest Neighbors (K-NNs) in the whitened PCA space and thus exclude most of samples which are distant to the probe. In the second stage, we maximize the “local” scatter by performing whitened PCA on the K nearest samples, which could explore the most discriminative information for similar classes. Moreover, block-based scheme is incorporated to address the small sample problem. This two-stage process is actually a coarse-to-fine scheme that can maximize both global and local scatter, and thus overcomes the aforementioned shortcomings of PCA. Experimental results on FERET face database show that our proposed algorithm is better than several representative approaches.

Let (X,Y) be a Rd R-valued random vector. In regression analysis one wants to estimate the regression function m(x):=E(Y|X=x) from a data set. In this paper we consider the convergence rate of the error for the k nearest neighbor estimators in case that m is (p,C)-smooth. It is known that the minimax rate is unachievable by any k nearest neighbor estimator for p > 1.5 and d=1. We generalize this result to any d ≥ 1. Throughout this paper, we assume that the data is independent and identically distributed and as an error criterion we use the expected L2 error.

Nearest neighbor search (NNS) among large-scale and high-dimensional vectors plays an important role in recent large-scale multimedia search applications. This paper proposes an optimized multiple codebook construction method for an approximate NNS scheme based on product quantization, where sets of residual sub-vectors are clustered according to their distribution and the codebooks for product quantization are constructed from these clusters. Our approach enables us to adaptively select the number of codebooks to be used by trading between the search accuracy and the amount of memory available.

Although a large number of query processing algorithms in spatial network database (SNDB) have been studied, there exists little research on route-based queries. Since moving objects move only in spatial networks, route-based queries, like in-route nearest neighbor (IRNN), are essential for Location-based Service (LBS) and Telematics applications. However, the existing IRNN query processing algorithm has a problem in that it does not consider time and space constraints. Therefore, we, in this paper, propose IRNN query processing algorithms which take both time and space constraints into consideration. Finally, we show the effectiveness of our IRNN query processing algorithms considering time and space constraints by comparing them with the existing IRNN algorithm.

This paper presents a novel algorithm for Nearest Neighbor (NN) classifier. NN classification is a well-known method of pattern classification having the following properties: * it performs maximum-margin classification and achieves less than twice the ideal Bayesian error, * it does not require knowledge of pattern distributions, kernel functions or base classifiers, and * it can naturally be applied to multiclass classification problems. Among the drawbacks are A) inefficient memory use and B) ineffective pattern classification speed. This paper deals with the problems A and B. In most cases, NN search algorithms, such as k-d tree, are employed as a pattern search engine of the NN classifier. However, NN classification does not always require the NN search. Based on this idea, we propose a novel algorithm named k-d decision tree (KDDT). Since KDDT uses Voronoi-condensed prototypes, it consumes less memory than naive NN classifiers. We have confirmed that KDDT is much faster than NN search-based classifier through a comparative experiment (from 9 to 369 times faster than NN search based classifier). Furthermore, in order to extend applicability of the KDDT algorithm to high-dimensional NN classification, we modified it by incorporating Gabriel editing or RNG editing instead of Voronoi condensing. Through experiments using simulated and real data, we have confirmed the modified KDDT algorithms are superior to the original one.

To prevent blindness from diabetic retinopathy, periodic screening and early diagnosis are neccessary. Due to lack of expert ophthalmologists in rural area, automated early exudate (one of visible sign of diabetic retinopathy) detection could help to reduce the number of blindness in diabetic patients. Traditional automatic exudate detection methods are based on specific parameter configuration, while the machine learning approaches which seems more flexible may be computationally high cost. A comparative analysis of traditional and machine learning of exudates detection, namely, mathematical morphology, fuzzy c-means clustering, naive Bayesian classifier, Support Vector Machine and Nearest Neighbor classifier are presented. Detected exudates are validated with expert ophthalmologists' hand-drawn ground-truths. The sensitivity, specificity, precision, accuracy and time complexity of each method are also compared.

This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.

This paper proposes a novel algorithm for image feature extraction-the dual two-dimensional fuzzy class preserving projections ((2D)2FCPP). The main advantages of (2D)2FCPP over two-dimensional locality preserving projections (2DLPP) are: (1) utilizing the fuzzy assignation mechanisms to construct the weight matrix, which can improve the classification results; (2) incorporating 2DLPP and alternative 2DLPP to get a more efficient dimensionality reduction method-(2D)2LPP.

This letter proposes a Cell-based Hybrid Index (CHI) for energy conserving k Nearest Neighbor search on air. The proposed CHI provides global knowledge on data distribution for fast decision of the search space and local knowledge for efficient pruning of data items. Simulations show that CHI outperforms the existing indexing schemes in terms of tuning time and energy efficiency. With respect to access time, it outperforms them except the distributed indexing scheme optimized for access time.

It is observed, surprisingly, that existing nearest neighbor search methods in wireless data broadcast may not work effectively on mobile clients with very limited memory space. To resolve this problem, a novel method for nearest neighbor search is introduced in the context of a representative of indexes, the grid-partition index, in wireless data broadcast. In the proposed scheme, a mobile client performs the nearest neighbor search by making a sequential access to index packets according to their broadcast order over a wireless channel. The performance evaluation demonstrates that our approach substantially outperforms limited memory versions of existing methods in terms of access time, while retaining a good energy conservation.

This letter proposes a fast k nearest neighbors search algorithm based on the wavelet transform. This technique exploits the important information of the approximation coefficients of the transform coefficient vector, from which we obtain two crucial inequalities that can be used to reject those vectors for which it is impossible to be k nearest neighbors. The computational complexity for searching for k nearest neighbors can be largely reduced. Experimental results on texture classification verify the effectiveness of our algorithm.

This paper presents a personal identification method based on BMME and LDA for images acquired at anterior and posterior occlusion expression of teeth. The method consists of teeth region extraction, BMME, and pattern recognition for the images acquired at the anterior and posterior occlusion state of teeth. Two occlusions can provide consistent teeth appearance in images and BMME can reduce matching error in pattern recognition. Using teeth images can be beneficial in recognition because teeth, rigid objects, cannot be deformed at the moment of image acquisition. In the experiments, the algorithm was successful in teeth recognition for personal identification for 20 people, which encouraged our method to be able to contribute to multi-modal authentication systems.

A novel fast KNN classification algorithm is proposed for pattern recognition. The technique uses one important feature, mean of the vector, to reduce the search space in the wavelet domain. Since the proposed algorithm rejects those vectors that are impossible to be the k closest vectors in the design set, it largely reduces the classification time and holds the classification performance as that of the original classification algorithm. The simulation on texture image classification confirms the efficiency of the proposed algorithm.

The classification time required by conventional multi-class SVMs greatly increases as the number of pattern classes increases. This is due to the fact that the needed set of binary class SVMs gets quite large. In this paper, we propose a method to reduce the number of classes by using nearest neighbor rule (NNR) in the principle component analysis and linear discriminant analysis (PCA+LDA) feature subspace. The proposed method reduces the number of face classes by selecting a few classes closest to the test data projected in the PCA+LDA feature subspace. Results of experiment show that our proposed method has a lower error rate than nearest neighbor classification (NNC) method. Though our error rate is comparable to the conventional multi-class SVMs, the classification process of our method is much faster.